package com.gemini.main.heap;

/**
 * gemini
 * com.gemini.main.heap.Heap
 *
 * 堆的一些概念
 * 堆是完全二叉树 叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树
 *
 * 1.可以用数组存储 节点i的两个子节点是2i 和 2i+1
 * 2.对于n+1个元素完全二叉树来说n/2+1到n的节点都是叶子节点（从第1个元素开始存储，第0个不存储）
 * 3.最大堆堆顶元素最大，最小堆堆顶元素最小
 * 4.求top K 问题中如果求top K 大元素，用小顶堆。求top K 小元素 ，用大顶堆。
 *
 * 例:求top K 大
 * 针对静态数据，如何在一个包含 n 个数据的数组中，查找前 K 大数据呢？
 * 我们可以维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出数据与堆顶元素比较。
 * 如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；
 * 如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。
 *
 * 求top K 小同理
 *
 * 堆的应用：如最小堆定时器，top K问题，
 * 合并有序小文件
 * 假设我们有 100 个小文件，每个文件的大小是 100MB，每个文件中存储的都是有序的字符串。我们希望将这些 100 个小文件合并成一个有序的大文件。这里就会用到优先级队列。
 *
 * 我们将从小文件中取出来的字符串放入到*小顶堆*中，那堆顶的元素，也就是优先级队列队首的元素，就是最小的字符串。
 * 我们将这个字符串放入到大文件中，并将其从堆中删除。然后再从小文件中取出下一个字符串，放入到堆中。
 * 循环这个过程，就可以将 100 个小文件中的数据依次放入到大文件中。
 *
 *
 * 删除堆顶数据和往堆中插入数据的时间复杂度都是o(log n)
 *
 *
 * @author zhanghailin
 */
public class Heap {
    private int[] a; // 数组，从下标 1 开始存储数据
    private int n;  // 堆可以存储的最大数据个数
    private int count; // 堆中已经存储的数据个数

    public Heap(int capacity) {
        a = new int[capacity + 1];
        n = capacity;
        count = 0;
    }

    /**
     * 插入元素（大顶堆）
     *
     * @param data
     */
    public void insert(int data) {
        if (count >= n) return; // 堆满了
        ++count;
        a[count] = data;
        int i = count;
        while (i / 2 > 0 && a[i] > a[i / 2]) { // 自下往上堆化
            swap(a, i, i / 2); // swap() 函数作用：交换下标为 i 和 i/2 的两个元素
            i = i / 2;
        }
    }

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    /**
     * 删除堆顶元素,
     */
    public void removeMax() {
        if (count == 0) return; // 堆中没有数据
        a[1] = a[count]; //将最后一个节点放入堆顶
        --count;
        heapify(a, count, 1);// 堆化
    }

    /**
     * @param a 完全二叉树数组
     * @param n 堆元素个数
     * @param i 从哪个位置开始堆化
     */
    private static void heapify(int[] a, int n, int i) { // 自上往下堆化
        while (true) {
            int maxPos = i;
            if (i * 2 <= n && a[i] < a[i * 2]) maxPos = i * 2; // 和左子树对比
            if (i * 2 + 1 <= n && a[maxPos] < a[i * 2 + 1]) maxPos = i * 2 + 1; // 和右子树对比
            // 两次比较是为了找出最大的元素，以便进行后面的交换
            if (maxPos == i) break; // 没有进行元素交换,其实意思就是 a[i] > a[i*2] && a[i] > a[i*2+1]
            swap(a, i, maxPos);// 交换元素
            i = maxPos;
        }
    }

    private static void buildHeap(int[] a, int n) {
        // 从第一个非叶子节点开始进行堆化 对于完全二叉树来说n/2+1到n的节点都是叶子节点
        for (int i = n / 2; i >= 1; --i) {
            heapify(a, n, i);
        }
    }



}

